#include <iostream>
#include <vector>
using namespace std;


//todo: use monotonic stack to optimize the code
class Solution
{

public:
    struct Node
    {
        int value;
        bool isGoodOddJump;
        bool isGoodEvenJump;
        int minValue;
        int maxValue;

        void print(int index)
        {
            cout << "i: " << index
                 << ", value: " << value
                 << ", odd: " << isGoodOddJump
                 << ", even: " << isGoodEvenJump
                 << ", minV: " << minValue
                 << ", maxV: " << maxValue << endl;
        }
    };
    int oddEvenJumps(vector<int> &arr)
    {
        std::vector<Node> dp(arr.size(), Node{false, false, 0, 0});
        dp[arr.size() - 1].value = arr[arr.size() - 1];
        dp[arr.size() - 1].isGoodOddJump = true;
        dp[arr.size() - 1].isGoodEvenJump = true;
        dp[arr.size() - 1].minValue = arr[arr.size() - 1];
        dp[arr.size() - 1].maxValue = arr[arr.size() - 1];

        for (int i = arr.size() - 2; i >= 0; i--)
        {
            dp[i].value = arr[i];
            // odd jump 奇数
            if (dp[i + 1].maxValue < arr[i])
            {
                dp[i].isGoodOddJump = false;
            }
            else
            {
                // find arr[j]>=arr[i] and argmin{arr[j]} and argmin{j}
                int index = -1;
                int value = -1;
                for (int j = i + 1; j < arr.size(); j++)
                {
                    if (arr[j] >= arr[i])
                    {
                        if (arr[j] < value || index == -1)
                        {
                            index = j;
                            value = arr[j];
                        }
                    }
                }
                dp[i].isGoodOddJump = (index == -1) ? false : dp[index].isGoodEvenJump;
            }
            // even jump 偶数
            if (dp[i + 1].minValue > arr[i])
            {
                dp[i].isGoodEvenJump = false;
            }
            else
            {
                // find arr[j]<=arr[i] and argmax{arr[j]} and argmin{j}
                int index = -1;
                int value = -1;
                for (int j = i + 1; j < arr.size(); j++)
                {
                    if (arr[j] <= arr[i])
                    {
                        if (arr[j] > value || index == -1)
                        {
                            index = j;
                            value = arr[j];
                        }
                    }
                }
                dp[i].isGoodEvenJump = (index == -1) ? false : dp[index].isGoodOddJump;
            }
            dp[i].maxValue = std::max(dp[i + 1].maxValue, arr[i]);
            dp[i].minValue = std::min(dp[i + 1].minValue, arr[i]);
        }
        int goodOddJumps = 0;
        int index = 0;
        for (Node node : dp)
        {
            node.print(index++);
            if (node.isGoodOddJump)
                goodOddJumps++;
        }
        return goodOddJumps;
    }
};

int main()
{
    cout << "Code975" << endl;
    Solution s;
    vector<int> arr2 = {2, 3, 1, 1, 4};
    vector<int> arr3 = {5, 1, 3, 4, 2};
    vector<int> arr4 = {14, 13, 15};
    cout << s.oddEvenJumps(arr2) << endl;
    return 0;
}